//    Copyright (C) Kherty.  All rights reserved.
using System.Collections.Generic;

namespace OpenLS.Spreadsheet
{
    class Graph<T>
    {
        public Node<T> AddData(T t)
        {
            var node = new Node<T>(t);
            nodeTable.Add(t, node);
            nodes.Add(node);
            return node;
        }

        public Node<T> this[T t] { get { return nodeTable[t]; } }
        public void AddEdge(Node<T> parent, Node<T> child)
        {
            parent.AddChild(child);
            child.AddParent(parent);
        }

        readonly Dictionary<T, Node<T>> nodeTable = new Dictionary<T, Node<T>>();
        readonly List<Node<T>> nodes = new List<Node<T>>();
        public List<Node<T>> SortAndRemove()
        {
            var rootNodes = new Queue<Node<T>>();
            foreach (Node<T> node in nodes)
                if (node.Parents.Count == 0)
                    rootNodes.Enqueue(node);
            var sorted = new List<Node<T>>();
            while (nodes.Count > 0)
            {
                if (rootNodes.Count == 0)
                {
                    return sorted;
                }

                // grab the first start node.
                Node<T> n = rootNodes.Dequeue();
                sorted.Add(n);
                var list = new List<Node<T>>(n.Children);
                for (int i = (n.Children.Count - 1); i >= 0; i--)
                {
                    Node<T> childNode = list[i];

                    n.RemoveChildNode(childNode);
                    if (childNode.Parents.Count == 0)
                    {
                        rootNodes.Enqueue(childNode);
                    }
                }
                nodes.Remove(n);
            }
            return sorted;
        }


        internal int Count
        {
            get
            {
                return nodes.Count;
            }
        }

        internal IEnumerable<Node<T>> GetNodes()
        {
            return nodes;
        }

        internal bool Contains(T c)
        {
            return nodeTable.ContainsKey(c);
        }
    }
}
